package jleda.tree;

public class BinaryHeapDouble {
	private static final int DEFAULT_SIZE = 8;
	private static final int RESIZE_FACTOR = 2;
	private double[] arr;
	private int size;
	
	public BinaryHeapDouble() {
		arr = new double[DEFAULT_SIZE];
		size = 0;
	}
	
	public void insert( double data ) {
		if( size+1 == arr.length ) {
			double[] t = new double[RESIZE_FACTOR*arr.length];
			System.arraycopy( arr, 1, t, 1, size );
			arr = t;
		}
		
		int hole = ++size;
		
		for( ; hole > 1 && data < arr[hole/2]; hole /= 2 ) {
			arr[hole] = arr[hole/2];
		}
		
		arr[hole] = data;
	}
	
	public double findMin() {
		return arr[1];
	}
	
	public double deleteMin() {
		double min = arr[1];
		
		int hole = 1, child;
		double t = arr[1] = arr[size];
		
		for( ; 2*hole < size; hole = child ) {
			child = 2*hole;
			
			if( child != size && arr[child+1] < arr[child] ) {
				child++;
			}
			
			if( arr[child] < t ) {
				arr[hole] = arr[child];
			} else {
				break;
			}
		}
		
		arr[hole] = t;
		size--;
		return min;
	}
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
}
